T1 分段 DP

Description

给定长度为 $n$ 的单调不减序列 $\{a\}$ 。定义一个区间的权值为区间长度与区间最小值的乘积。求将该序列分成 $k\in [1,n]$ 段的权值和的最大值。
$1\leq n\leq 2\times 10^5,1\leq a_i\leq 8\times 10^3$

Description

有一棵树，初始时只有 $4$ 个节点， $2\ 3\ 4$ 的父节点都是 $1$ 。 $q$ 次操作，每次给定一个点 $u$ 。设操作前点数为 $n$ ，那么本次操作就是将 $n+1$ 和 $n+2$ 连在 $u$ 上。操作后输出目前树的直径大小。

$q\leq 5\times 10^5$ 。

Solution

众所周知，在求解费用流的时由于要建反边，必然会有负权边的存在。所以费用流的通常写法是 EK+SPFA。
事实上我们是可以通过一些技巧，使得 dijkstra 也可以跑费用流。这样的好处是保证了复杂度的下限。
本文将探讨如何使得 dijkstra 可以跑费用流。

定义

定义 $E$ 为基础集，$\mathcal{I}$ 是由 $E$ 的子集构成的集族（子集的集合）。
元组 $(E,\mathcal{I})$ 构成了一个子集系统，当且仅当

阅读全文 »

T1

Description

给一个数列，长度为 $10^5$ 。划成 $20$ 段，每段权值为 #$\{i,j|a_i=a_j\}$。要求最小化权值和。

Solution

T1 大数

Description

给定一个长度为 $n$ 的十进制数 s 和一个质数 $p$ 。 $q$ 次询问，每次给定 $l\ r$ ，询问有多少十进制数 s[x:y] $(l\leq x\leq y\leq r)$ 能被 $p$ 整除。
$1\leq n,q\leq 2\times 10^5,p\leq 2\times 10^9$

Description

给定一个 $n$ 列的表格，每列的高度 $h_i$ 各不相同，但底部对齐，然后向表格中填入 $k$ 个相同的数，填写时要求不能有两个数在同一列。若两个数在同一行，但是中间某一列断开是被允许的，否则也不允许。求填数的方案数对 $10^9+7$ 取模的值。
$n\leq 500,h_i\leq 10^6$

Solution

T1 菜肴制作

Description

有 $n$ 道菜和有 $m$ 条要求，每条要求形如“A 号菜需要在 B 号菜的前面”。现在要求给出一个上菜序列，在满足所有要求的前提下，满足：

阅读全文 »

Description

给定一个串，把串分成偶数段，假设为 $s_1,s_2,\cdots,s_k$ ，要求满足 $s_1=s_k,s_2=s_{k-1},\cdots$ ，求方案数。
$n\leq 10^5$

Solution

source：区间本质不同子串(Luogu6292) 区间本质不同回文子串(bzoj5384)

两个问题都可以归结为「区间本质不同元素个数」。解决这个问题有两个十分常用的方法：

阅读全文 »